package com.wu.isbalancedsolution;

/**
 * 输入一棵二叉树，判断该二叉树是否是平衡二叉树。
 * 在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树
 */
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

/**
 * 思路：
 * 如果左右子树的高度的差超过1，则不是平衡二叉树
 * 后续遍历时，遍历到一个节点
 * 其左右子树已经遍历  依次自底向上判断，
 * 每个节点只需要遍历一次
 */
public class Solution {

    public static boolean isBalanced = true;

    public static boolean isBalancedSolution(TreeNode root) {
        getDepth(root);
        return isBalanced;
    }

    public static int getDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = getDepth(root.left);
        int right = getDepth(root.right);

        if (Math.abs(left - right) > 1) {
            isBalanced = false;
        }
        return right > left ? right + 1 : left + 1;
    }

    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);

        node1.left = node2;
        node2.left = node3;
        node3.left = node4;
        node4.left = node5;

        boolean balancedSolution = isBalancedSolution(node1);
    }
}